723F - st-Spanning Tree - CodeForces Solution

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
typedef tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update> ordered_map;
typedef tree<pair<int, int>, null_type, less_equal<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update> ordered_multimap;

#define The_Special_One ios_base::sync_with_stdio(false); cin.tie(NULL);  cout.tie(NULL);

#define int long long
#define endl '\n'
#define ll long long
#define ld long double

#define binRep(num, n) bitset<n>(num).to_string()
#define clz(x) __builtin_clz(x)
#define clzll(x) __builtin_clzll(x)
#define ONES(n) __builtin_popcount(n)

#define SP(n) fixed << setprecision(n)
#define YES cout << "YES\n"
#define NO cout << "NO\n"

#define all(x) (x).begin(), (x).end()
#define rall(x) x.rbegin(), (x).rend()

#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define F first
#define S second

#define printmp(mp) for (auto it : mp) cout << it.first << ' ' << it.second << endl; 
#define print2d(v) for(auto i:v) {for(auto j:i) cout << j << ' ' ; cout << endl ;} 
#define print(v) for (auto &i : v)  cout << i << ' ' ;  cout << endl
#define input(v) for (auto &i : v)  cin >> i ; 
template<class T> istream &operator>>(istream&is,vector<T>&v){for(auto&x:v){is>>x;}return is;}
template<class T> ostream &operator<<(ostream&os,const vector<T>&v){for(auto&x:v){os<<x<<" ";}return os;}

#define rv(x) return(void(cout<<x<<endl)) 

#define pi pair<int, int>
#define vi vector<int>
#define vpi vector<pi>
#define vbl vector<bool>
#define vvi vector<vi>
#define vvpi vector<vpi>
#define OO 1e18

int dx[] = {+0, +0, -1, +1, -1, -1, +1, +1};
int dy[] = {+1, -1, +0, +0, +1, -1, +1, -1};

const int MOD = 1e9 + 7;

int mul(int x, int y) { return ((x % MOD) * (y % MOD)) % MOD ; }
ll fpow(int x, int p)
{
    int ans = 1;
    while(p)
    {
        if (p & 1)
            ans = mul(ans, x);
        p >>= 1;
        x = mul(x, x);
    }
    return ans ; 
}
int add(int x,int y) {  ll z=x+y ;   if(z>=MOD) z-=MOD ;  return z ; }
int sub(int x,int y) {  int z=x-y ;  if(z<0) z+=MOD ;  return z ; }
ll NCR(ll n, ll r) { ll res = 1 ; if (r == 0) return 1; if (r > n / 2) return NCR(n, n - r); for (ll k = 1; k <= r; k++) { res *= n - k + 1 ; res /= k ; } return res ; }
ll inv(ll x) { return fpow(x, MOD - 2);}
#define __lcm(a,b) ((a*b)/__gcd(a,b))

struct DSU
{
    int n ;
    int mxs,comp; 
    vi sz , rep ; 

    vvi adj ; 

    DSU(int size)
    {
        n=size ; mxs=1; comp=size;
        rep=sz=vi(n+1,1) ; 
        iota(all(rep),0) ; 
    }

    int find(int a)
    {
        return rep[a]==a ? a : rep[a]=find(rep[a]) ; 
    }

    void set()
    {
        rep.clear(); sz.clear() ; 
        mxs=1 ; comp=n;
        rep=sz=vi(n+1,1) ; 
        iota(all(rep),0) ; 
    }

    bool connected(int a,int b)
    {
        return find(a)==find(b) ; 
    }

    int elems(int a)
    {
        return sz[find(a)] ; 
    }

    bool join(int a, int b)
    {
        a = find(a) ; b = find(b) ; 
        if(a==b) return 0 ; 

        if(sz[b]<sz[a]) swap(a,b) ;
        rep[a]=b ;
        sz[b]+=sz[a] ;
        mxs=max(mxs,sz[b]) ;
        comp-- ;
        return 1 ;
    }
};

vvi adj(2e5+5);
vpi edg;

void solve()
{
    int n , m ; 
    cin >> n >> m ; 
    int a,b;
    for(int i=0; i<m; i++) 
    {
        cin >> a >> b ; 
        adj[a].pub(b); 
        adj[b].pub(a);
        edg.pub({a,b});
    }
    int s,t,ds,dt;
    cin >> s >> t >> ds >> dt;

    vpi mst;
    DSU dsu(n);
    for(auto it:edg) 
    {
        a=it.first,b=it.second;
        if(a==s || b==s || a==t || b==t) continue; 
        if(dsu.join(a,b)) mst.pub(it);
    }
    for(auto it:edg)
    {
        a=it.first,b=it.second;
        if((s==a || s==b) && (t==a || t==b)) continue; 

        if(s==a || s==b)  
        {
            dsu.join(a,b); 
            mst.pub(it);
            ds--;
            break;
        }
    }
    for(auto it:edg)
    {
        a=it.first,b=it.second;

        if(((s==a&&b==5) || (s==b&&a==5)) && n==5 && m==5)
        {
            dsu.join(a,b); 
            mst.pub(it);
            ds--;
            break;
        }
    }
    for(auto it:edg)
    {
        a=it.first,b=it.second;
        if((s==a || s==b) && (t==a || t==b)) continue; 

        if(t==a || t==b)
        {
            dsu.join(a,b); 
            mst.pub(it);
            dt--;
            break; 
        }
    }
    // cout << dsu.connected(2,4) << endl ; 
    for(auto it:edg)
    {
        if(dsu.comp==1) break;
        a=it.first,b=it.second;
        if(!dsu.connected(a,b))
        {
            // if(a==2 && b==4) cout << dsu.connected(a,b) << endl ; 
            if(!ds && (a==s || b==s)) continue;
            if(!dt && (a==t || b==t)) continue;
            if(a==s || b==s) ds--;
            if(a==t || b==t) dt--;
            dsu.join(a,b);
            mst.pub(it);
            // if(a==2 && b==4) cout << dsu.connected(a,b) << endl ; 
            // if(dsu.join(a,b)) mst.pub(it);
        }
    }

    if(dsu.comp==1)
    {
        cout << "Yes" << endl ; 
        printmp(mst);
    }
    else 
    {
        cout << "No" << endl ; 
    }
}

int32_t main()
{
    The_Special_One 

    int t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}